import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/8 16:17
 * @description 字典树
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        List<String> dic = new ArrayList<>();
        dic.add("cat");
        dic.add("bat");
        dic.add("rat");
        dic.add("cate");
        solution2.replaceWords(dic, "the cattle was rattled by the battery");
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        Trie node = new Trie();
        for (String dic : dictionary) {
            node.insert(dic);
        }
        String[] se = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String temp : se) {
            int len = node.findPrefix(temp);
            if (len != -1) {
                sb.append(temp, 0, len).append(" ");
            } else {
                sb.append(temp).append(" ");
            }
        }
        return sb.substring(0, sb.length() - 1);
    }

}
class Trie{
    Trie[] children;
    boolean isEnd;
    public Trie() {
        this.children = new Trie[26];
        this.isEnd = false;
    }
    public void insert(String word) {
        Trie root = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (root.children[index] == null) {
                root.children[index] = new Trie();
            }
            root = root.children[index];
        }
        root.isEnd = true;
    }
    public int findPrefix(String word) {
        int ans = 0;
        Trie root = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (root.isEnd) {
                return ans;
            }
            if (root.children[index] == null) {
                break;
            }
            root = root.children[index];
            ans++;
        }
        return -1;
    }
}
